//你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指
//相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。 
// 示例： 
// 输入：
//[
//  [0,2,1,0],
//  [0,1,0,1],
//  [1,1,0,1],
//  [0,1,0,1]
//]
//输出： [1,2,4]
// 
// 提示： 
// 
// 0 < len(land) <= 1000 
// 0 < len(land[i]) <= 1000 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵 👍 170 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-09-10 22:53:24
 * @description 面试题 16.19.水域大小
 */
public class PondSizesLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 PondSizesLcci fun=new PondSizesLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] pondSizes(int[][] land) {
        List<Integer> ans=new ArrayList<>();
		for (int i = 0; i < land.length; i++) {
			for (int j = 0; j < land[i].length; j++) {
				if(land[i][j]==0){
					ans.add(dfs(land,i,j));
				}
			}
		}
        return ans.stream().sorted().mapToInt(Integer::intValue).toArray();
    }
	int [] dx={0,0,1,-1,1,1,-1,-1};
	int [] dy={1,-1,0,0,1,-1,1,-1};
	private int dfs(int[][] land, int i, int j) {
		// 边界检查或非水域检查
		if (i < 0 || i >= land.length || j < 0 || j >= land[0].length || land[i][j] != 0) {
			return 0;
		}

		// 标记为已访问（用-1或其他非0值）
		land[i][j] = -1;
		int size = 1; // 当前单元格

		// 递归搜索所有8个方向
		for (int k = 0; k < dx.length; k++) {
			int x = i + dx[k];
			int y = j + dy[k];
			size += dfs(land, x, y);
		}

		return size;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
